package leetCode;

public class Q912 {
    public int[] sortArray(int[] nums) {
        heapSort(nums);
        return nums;
    }

    public void heapSort(int[] nums) {
        int len = nums.length - 1;
        buildMaxHeap(nums, len);
        for (int i = len; i >= 1; --i) {
            swap(nums, i, 0);
            len -= 1;
            maxHeapify(nums, 0, len);
        }
    }

    // 构造大根堆
    public void buildMaxHeap(int[] nums, int len) {
        for (int i = len / 2; i >= 0; --i) maxHeapify(nums, i, len);
    }

    //堆排序（最大堆调整）
    public void maxHeapify(int[] nums, int i, int len) {
        for (; (i << 1) + 1 <= len;) {//向左子树移动
            int lson = (i << 1) + 1;
            int rson = (i << 1) + 2;
            int large;
            //如果左儿子大于根节点
            if (lson <= len && nums[lson] > nums[i]) large = lson;
            else large = i;
            //右儿子大于根节点
            if (rson <= len && nums[rson] > nums[large]) large = rson;
            if (large != i) {
                swap(nums, i, large);
                i = large;
            } else break;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 这是力扣找的容易理解的版本
     * @param nums
     */
    public int[] heapSort2(int[] nums) {
        int len = nums.length;
        // 构造大根堆
        for (int i = len/2-1; i >=0; i--) {// 从叶子结点的父节点开始调整
            adjust(nums, len, i);
        }

        //根节点和数组依次从后往前交换
        for (int i = len - 1; i >= 1; i--) {
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;
            adjust(nums, i, 0);
        }
        return nums;
    }
    void adjust(int []nums, int len, int rootIndex) {
        // 递归调整根节点为rootIndex的大根堆
        int l = 2 * rootIndex + 1;
        int r = 2 * rootIndex + 2;
        int maxIndex = rootIndex;
        if (l<len&&nums[l]>nums[maxIndex])maxIndex = l;//左孩子比根节点大
        if (r<len&&nums[r]>nums[maxIndex])maxIndex = r;//右孩子比根节点大
        if (maxIndex != rootIndex) {//需要调整
            int temp = nums[maxIndex];
            nums[maxIndex] = nums[rootIndex];
            nums[rootIndex] = temp;
            adjust(nums, len, maxIndex);
        }
    }

    public static void main(String[] args) {
        for (int i : new Q912().heapSort2(new int[]{5, 9, 1, 4, 7, 2, 3, 4, 5, 8, 5, 2})) {
            System.out.println(i);
        }
    }
}
